
#include <stdint.h>
#include <cstddef>    // for NULL
#include <string.h>
#include "RBTree.h"

int is_red ( spRBNode_t root )
{
   return root != NULL && root->red == 1;
}

spRBNode_t jsw_single ( spRBNode_t root, int dir )
{
    spRBNode_t save = root->link[!dir];
  
    root->link[!dir] = save->link[dir];
    save->link[dir] = root;
  
    root->red = 1;
    save->red = 0;
 
   return save;
}
 
spRBNode_t jsw_double ( spRBNode_t root, int dir )
{
   root->link[!dir] = jsw_single ( root->link[!dir], !dir );
   return jsw_single ( root, dir );
}

spRBNode_t make_node ( unsigned long data )
{
   spRBNode_t rn = new jsw_node;
 
   if ( rn != NULL ) {
     rn->data = data;
     rn->red = 1; /* 1 is red, 0 is black */
     rn->link[0] = NULL;
     rn->link[1] = NULL;
   }
 
   return rn;
}

spRBNode_t find_node (spRBNode_t root, unsigned long data )
{ 
   if ( root != NULL ) 
   {
      if (root->data == data) return root;
      else if (data>root->data) return find_node(root->link[1],data);
      else if (data<root->data) return find_node(root->link[0],data);
   }
   else return NULL;
}

spRBNode_t jsw_insert_r ( spRBNode_t root, unsigned long data )
{
   if ( root == NULL )
     root = make_node ( data );
   else if ( data != root->data ) {
     int dir = root->data < data;
 
     root->link[dir] = jsw_insert_r ( root->link[dir], data );
 
     /* Hey, let's rebalance here! */
     if ( is_red ( root->link[dir] ) ) 
     {
         if ( is_red ( root->link[!dir] ) ) 
         {
             /* Case 1 */
             root->red = 1;
             root->link[0]->red = 0;
             root->link[1]->red = 0;
         }
         else 
         {
             /* Cases 2 & 3 */
             if ( is_red ( root->link[dir]->link[dir] ) )
               root = jsw_single ( root, !dir );
             else if ( is_red ( root->link[dir]->link[!dir] ) )
               root = jsw_double ( root, !dir );
         }
     }
   }
 
   return root;
}
 
int jsw_insert ( spRBTree_t tree, unsigned long data )
{
   tree->root = jsw_insert_r ( tree->root, data );
   tree->root->red = 0;
   return 1;
}

//int jsw_insert ( spRBTree_t tree, int data )
//{
//   if ( tree->root == NULL ) 
//   {
//       /* Empty tree case */
//       tree->root = make_node ( data );
//       if ( tree->root == NULL )
//          return 0;
//   }
//   else 
//   {
//       struct jsw_node head = {0}; /* False tree root */
//   
//       spRBNode_t g, *t;     /* Grandparent & parent */
//       spRBNode_t p, *q;     /* Iterator & parent */
//       int dir = 0, last;
//   
//       /* Set up helpers */
//       t = &head;
//       g = p = NULL;
//       q = t->link[1] = tree->root;
//   
//       /* Search down the tree */
//       for ( ; ; ) 
//       {
//           if ( q == NULL ) 
//           {
//               /* Insert new node at the bottom */
//               p->link[dir] = q = make_node ( data );
//               if ( q == NULL )
//                  return 0;
//           }
//           else if ( is_red ( q->link[0] ) && is_red ( q->link[1] ) ) 
//           {
//               /* Color flip */
//               q->red = 1;
//               q->link[0]->red = 0;
//               q->link[1]->red = 0;
//           }
//     
//           /* Fix red violation */
//           if ( is_red ( q ) && is_red ( p ) ) 
//           {
//               int dir2 = t->link[1] == g;
//       
//               if ( q == p->link[last] )
//                  t->link[dir2] = jsw_single ( g, !last );
//               else
//                  t->link[dir2] = jsw_double ( g, !last );
//           }
//     
//           /* Stop if found */
//           if ( q->data == data )
//               break;
//     
//           last = dir;
//           dir = q->data < data;
//     
//           /* Update helpers */
//           if ( g != NULL )
//              t = g;
//           g = p, p = q;
//           q = q->link[dir];
//       }
//   
//       /* Update root */
//       tree->root = head.link[1];
//   }
// 
//   /* Make root black */
//   tree->root->red = 0;
// 
//   return 1;
//}